"""
使用贪心算法解决集合覆盖问题
题目源于《算法图解》p123
"""

# set：集合，支持集合的并，交，差运算；集合中不会出现重复的元素
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])

stations = dict()
stations["knoe"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])

final_stations = set()

# print(stations.keys())
# print(stations.values())
# print(stations.items())
"""
这里展示了 哈希表的三个函数，如果进行打印，结果分别为：
dict_keys(['knoe', 'ktwo', 'kthree', 'kfour', 'kfive'])
dict_values([{'id', 'ut', 'nv'}, {'wa', 'mt', 'id'}, {'or', 'ca', 'nv'}, {'ut', 'nv'}, {'az', 'ca'}])
dict_items([('knoe', {'id', 'ut', 'nv'}), ('ktwo', {'wa', 'mt', 'id'}), ('kthree', {'or', 'ca', 'nv'}), ('kfour', {'ut', 'nv'}), ('kfive', {'az', 'ca'})])
.keys()输出的是键的队列
.values()输出的是值形成的集合的队列
.items()则是输出一个键-值对

key, value = dict.item() 表示分别获取这个字典元素中的键和对应的值的集合
"""

def find_smallest_set(states_needed):
    while states_needed:    # 集合不为空
        to_cover = set()    # 本次state要覆盖的
        covered = set()
        best_choice = None
        for state, stations_for_states in stations.items():
            covered = stations_for_states & states_needed
            if len(covered) > len(to_cover):
                to_cover = covered
                best_choice = state
        states_needed -= to_cover
        final_stations.add(best_choice)

find_smallest_set(states_needed)
print(final_stations)

